package leetcode;

/**
 * Created by Ghost on 2014/12/20.
 */
public class Edit_Distance {
    private int min(int a,int b,int c){
        int first = Math.min(a,b);
        return Math.min(first,c);
    }
    public int minDistance(String word1, String word2) {

        int m = word1.length();
        int n = word2.length();
        if(m==0)
            return n;
        if(n==0)
            return m;
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int[][] w = new int[m][n];

        for(int i=0;i<n;i++){
            if(i>0){
                w[0][i]= Math.min(w[0][i-1]+1,i+(w1[0]==w2[i]?0:1));
            }
            else{
                w[0][i]=w1[0]==w2[i]?0:1;
            }
        }

        for(int i=0;i<m;i++){
            if(i>0){
                w[i][0] = Math.min(w[i-1][0]+1,i+(w1[i]==w2[0]?0:1));
            }
            else{
                w[i][0] = w1[i]==w2[0]?0:1;
            }
        }


        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                w[i][j]=min(w[i-1][j]+1,w[i][j-1]+1,w[i-1][j-1]+(w1[i]==w2[j]?0:1));
            }
        }
        return w[m-1][n-1];
    }

    public static void main(String[] args){
        Edit_Distance edit_distance = new Edit_Distance();
        System.out.println(edit_distance.minDistance("o","o"));
    }
}
